HW#5 --- last modified February 28 2019 22:25:56..

Solution set.

Due date: May 11

Files to be submitted:
  Hw5.zip

Purpose: To learn about unification and typing algorithms. To experiment with C's setjmp function.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO9 -- Understand type systems.

LO10 -- Understand the implementation of procedure calls and stack frames.

Specification:

This homework will consist of two parts an ML part and a C part. Both parts should be submitted in the file Hw5.zip.

For the ML part, I want you to experiment with coding a unification algorithm. All of the code for this part of the homework can be in Hw5.sml . Be sure to list all of your group members and their IDs in the comment at the start of the file. Then define a ML signature TypeSystem and an ML Module an SimpleTypes which makes use of this signature. Your ML module should have in it a recursive data type my_types . Here are the conditions which define a my_types type: (1) Var of type string is a my_types, (2) Number is a my_types, (3) if a and b are my_types so is Function(a,b) , (4) if a and b are my_types so is Product(a,b). In addition, to the recursive type, I would like your module to support at least two functions concerned with typing that we discussed in class. I'll leave one up to you. The other, however, has to be an implementation of the unification function. This function, unify(a,b) takes two my_types elements and prints a most general unifier for them (based on the three conditions we went over at the end of April 27) if it exists; otherwise, it prints "No unifier for a and b exists".

For the C part of the homework, I'd like you to put your code in count.c In that file write the function that results from converting the function

fun count 0 b = b | count a b = count (a - 1) (b + 1);

to C. I would like you to set up your driver program so that when the grader runs it with a command line argument with a line like:

./count a b

it would invoke your count function with arguments a and b. Next I would like you to modify count so that when the base condition is met, it not only returns and prints the output, but it also calls setjmp to get a jmp_buf struct. I would then like you to have the program output a hexadecimal dump for each member of this struct/array. You should also print out the contents of the stack from its start to the frame pointer stored in jmp_buf. Next I would like you to test your code on different values of a and b and to see where the two variables gets stored in a given stack frame and in general to figure out the format of C function calls through experimentation. Write up these results in write_up.txt and put them in your ZIP file as well.

Point Breakdown